package leetcode.pre50.Code39_40组合问题;

import java.util.*;

/**
 * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * <p>
 * 说明：解集不能包含重复的子集。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,2]
 * 输出:
 * [
 * [2],
 * [1],
 * [1,2,2],
 * [2,2],
 * [1,2],
 * []
 * ]
 * <p>
 * 注：在这种要求不能重复组合的情况下，当前位置要和不要的方法一般不能用
 *
 * @since 2019/11/29 0029 下午 11:19
 */
public class Code01_组合数2_有重复数组的子集 {


    public static void main(String[] args) {
        int[] arr = {1, 1, 2};
        combination1(arr);
        for (List<Integer> list : res) {
            System.out.println(list);
        }
    }

    public static List<List<Integer>> res = new LinkedList<>();

    public static List<List<Integer>> combination1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return res;
        }
        //利用栈只是为了存储当前的结果。
        Stack<Integer> stack = new Stack<>();
        //注意这里要排序 ，目的是为了让判断重复过程简单。
        //如果题目给的arr是String或char数组，也要先排序，方法一样
        Arrays.sort(arr);
        process(arr, 0, stack);
        return res;
    }

    /**
     * [1,1,2]输出顺序为：
     * []
     * <p>
     * [1][1, 1][1, 1, 2]
     * <p>
     * [1, 2]
     * <p>
     * [2]
     */
    private static void process(int[] arr, int index, Stack<Integer> stack) {
        //如果要求不能是空，则在这里判断一下，stack是否size为0
        res.add(new ArrayList<>(stack));
        if (index >= arr.length) {
            return;
        }
        for (int i = index; i < arr.length; i++) {
            //{1,1,2,3} 在当前index = 0情况下，第1个1已经和后面的2,3发生所有组合了，所以第2个1跳过
            //也就是说当第1个1 pop后，第2个1直接跳过。当第1个1正在用，第2个1可以和第1个1组合。
            if (i > index && arr[i] == arr[i - 1]) {
                continue;
            }
            stack.push(arr[i]);
            process(arr, i + 1, stack);
            stack.pop();
        }
    }



}
